import sys

class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        dp = {}
        for i in range(len(s)):
            begin = i
            end = i
            while begin>=0 and end<len(s) and s[begin]==s[end]:
                #add palindrome with odd size
                if end not in dp:
                    dp.update({end:[begin]})
                else:
                    dp[end].append(begin)
                begin -= 1
                end += 1
            begin = i
            end = i+1
            while begin>=0 and end<len(s) and s[begin]==s[end]:
                #add palindrome with even size
                if end not in dp:
                    dp.update({end:[begin]})
                else:
                    dp[end].append(begin)
                begin -= 1
                end += 1
        endWithMinCut ={ key: sys.maxsize for key in dp.keys() }
        ends = list(dp.keys())
        ends.sort()
        for end in ends:
            minCut = sys.maxsize
            for begin in dp[end]:
                lastEnd = begin-1
                if lastEnd==-1:
                    minCut = min(minCut, 0)
                else:
                    minCut = min(minCut, endWithMinCut[lastEnd]+1)
            endWithMinCut[end] = minCut
        return endWithMinCut[len(s)-1]

print(Solution().minCut("aab"))